Semiconductor integrated circuits are traditionally designed and fabricated by first preparing a schematic diagram or hardware description language (HDL) specification of a logical circuit in which functional elements are interconnected to perform a particular logical function. With standard cell technology, the schematic diagram or HDL specification is synthesized into standard cells of a specific cell library.
Each cell corresponds to a logical function unit, which is implemented by one or more transistors that are optimized for the cell. The logic designer selects the cells according to the number of loads that are attached to the cell, as well as an estimated interconnection required for routing. The cells in the cell library are defined by cell library definitions. Each cell library definition includes cell layout definitions and cell characteristics. The cell layout definition includes a layout pattern of the transistors in the cell, geometry data for the cell's transistors and cell routing data. The cell characteristics include a cell propagation delay and a model of the cell's function. The propagation delay is a function of the internal delay and the output loading (or “fan-out”) of the cell.
A series of computer-aided design tools generate a netlist from the schematic diagram or HDL specification of the selected cells and the interconnections between the cells. The netlist is used by a floor planner or placement tool to place the selected cells at particular locations in an integrated circuit layout pattern. The interconnections between the cells are then routed along predetermined routing layers. The design tools then determine the output loading of each cell as a function of the number of loads attached to each cell, the placement of each cell and the routed interconnections.
A timing analysis tool is then used to identify timing violations within the circuit. The time it takes for a signal to travel along a particular path or “net” from one sequential element to another depends on the number of cells in the path, the internal cell delay, the number of loads attached to the cells in the path, the length of the routed interconnections in the path and the drive strengths of the transistors in the path.
A timing violation may be caused by a number of factors. For example, a particular cell may not have a large enough drive strength to drive the number of loads that are attached to that cell. Also, exceptionally long routing paths may cause timing violations. Timing violations are eliminated by making adjustments at each stage in the layout process. For example, the logic diagram can be changed to restructure certain sections of logic to improve timing through that section. In addition, an under-driven cell may be fixed by changing the logic diagram to include a cell having a larger drive strength. An exceptionally long routing path can be corrected by adjusting the placement of the cells. Other changes can also be made
Once the timing violations have been corrected, the netlist, the cell layout definitions, the placement data and the routing data together form an integrated circuit layout definition, which can be used to fabricate the integrated circuit.
Logic restructuring is one of the basic steps in optimizing the timing of a chip design. The purpose of logic restructuring is to find a chip design that has an identical logic function of an original chip design but has reduced propagation delays through the circuit. In order to perform a logic restructuring of the original chip design, chip designers apply an algorithm to create a design with a logic function identical to the logic function of the original design. If the new design is more efficient than the original design, the new design will replace the old design. This is shown in U.S. Patent Application Publication No. 11/041 562[Corresponding with LSI Gasanov et al. “Graph Identities in Integrated Chip Resynthesis”], which is incorporated by reference into this disclosure. An identity set is created with identical schemes, i.e., logically equivalent systems of cells. The identity set is a set of rules where each rule includes two parts. Each part is a scheme, and schemes that are parts of one rule are logically identical. If a portion of the original chip design is included in the identity set then that portion, or scheme, can be replaced with another scheme in the identity set.
Due to the large number of components and details required, logic restructuring is not practical without the aid of computers. But even when implemented with computers, the algorithms are slow on large designs. The algorithms would work more efficiently if applied to only selected appropriate parts of the integrated circuit, and thus there is a need for a way to select the appropriate parts of an integrated circuit for logic restructuring.